package com.sourcetrip.algorithm.inter;

import com.sourcetrip.my.modle.EdgeInfo;
import com.sourcetrip.my.modle.PathInfo;
import com.sourcetrip.utils.Visitor;

import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * @author: ZhouBert
 * @date: 2021/1/8
 * @description:	（有向）图接口设计
 * V - 顶点的 value
 * E - 顶点的权重
 */
public interface Graph<V, E> {

	/**
	 * 返回 定点的个数
	 * @return
	 */
	int verticesSize();

	/**
	 * 返回 边的数量
	 * @return
	 */
	int edgesSize();

	/**
	 * 添加 顶点
	 */
	void addVertex(V v);

	/**
	 * 删除顶点
	 */
	void removeVertex(V v);

	/**
	 * 添加边
	 * @param fromV	出来的顶点
	 * @param toV	到达的顶点
	 */
	void addEdge(V fromV, V toV);

	/**
	 * 添加边
	 * @param fromV	从 from 出来的顶点
	 * @param toV	到 to 的顶点
	 * @param weight	权重
	 */
	void addEdge(V fromV, V toV, E weight);

	/**
	 * 删除边
	 * @param fromV	边的起始顶点
	 * @param toV	边的到达顶点
	 */
	void removeEdge(V fromV , V toV);


	/**
	 * 打印图中的顶点（Vertex）和 边（Edge）的信息
	 */
	void print();

	/**
	 * breadth first search
	 * 广度优先遍历
	 * @param begin	遍历的顶点（从不同的顶点访问的效果不一样，有可能不会遍历到所有的顶点）
	 * @param visitor	访问器
	 */
	void bfs(V begin, Visitor<V> visitor);

	/**
	 * depth first search
	 * 深度优先遍历
	 * @param begin	遍历的顶点（从不同的顶点访问的效果不一样，有可能不会遍历到所有的顶点）
	 * @param visitor	访问器
	 */
	void dfs(V begin, Visitor<V> visitor);

	/**
	 * 拓扑（topological）排序
	 * @return
	 */
	List<V> topologicalSort();

	/**
	 * Minimum Spanning Tree
	 * 最小生成树
	 * @return
	 */
	Set<EdgeInfo<V, E>> mst();

	/**
	 * 最短路径算法
	 * 从一个顶点出发，到图中其他顶点的路径集合
	 * @param vertexBegin	起始顶点
	 * @return
	 */
	Map<V, PathInfo<V, E>> shortestPath(V vertexBegin);


	/**
	 * 边的权重拓展接口
	 * @param <E>
	 */
	public interface WeightManager<E> {
		/**
		 * 比较两个权重
		 * @param w1
		 * @param w2
		 * @return
		 */
		int compare(E w1, E w2);

		/**
		 * 权重的增加
		 * @param w1
		 * @param w2
		 * @return
		 */
		E add(E w1, E w2);

		/**
		 * 权重减法
		 * w1- w2
		 * @param w1
		 * @param w2
		 * @return
		 */
		E minus(E w1, E w2);

		E zero();
	}
}
